package cyc2018.贪心思想;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * 根据身高重建队列
 * 总结：先按照 h 降序排序，再按照 k 升序排序，得到的是 h、k 的有序序列
 *      然后以 k 为 index，将当前的 people 保存到 List 里面，借助 List 自动排序的功能为各个 people 选取位置
 */
public class Test406 {

    public static int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                // 按照身 h 降序 K升序排序
                return o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0];
            }
        });
        List<int[]> result = new ArrayList<>(people.length);
        // [h, k]中 k 表示比前面大于等于 h 的个数
        // 所以：以 k 为 index 往 List 里面存放本 [h,k]
        for (int[] p : people) {
            result.add(p[1], p);
        }
        return result.toArray(people);
    }

    /**
     * Input:
     * [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
     * 排序结果为：
     * [70、71、61、50、52、44]
     * 然后遍历每一个元素，以该元素的1号位置的值为下标往list里面存放本元素
     * [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
     *
     * @param args
     */

    public static void main(String[] args) {
        int[][] people = {{7, 0}, {4, 4}, {7, 1}, {5, 0}, {6, 1}, {5, 2}};
        int[][] answer = reconstructQueue(people);
        for (int i = 0; i < answer.length; i++) {
            System.out.print("[");
            for (int j = 0; j < answer[0].length; j++) {
                System.out.print(answer[i][j]);
            }
            System.out.print("]" + " ");
        }
    }
}
